#include<string>
using namespace std;
class Solution {
private:
	void getNext(int* next, const string& p) {
		next[0] = -1;
		int i = 0, k = -1;
		while (i < p.size() - 1) {
			if (k == -1 || p[i] == p[k]) {
				next[++i] = ++k;
			}
			else {
				k = next[k];
			}
		}
	}
	int find(const string& t, const string& p) {
		if (p.size() < 1) return 0;
		int* next = new int[p.size()];
		getNext(next, p);
		int i = 0;
		int j = 0;
		int tlen = t.length();
		int plen = p.length();
		while (i < tlen && j < plen) {
			if (j == -1 || p[j] == t[i]) {
				++i;
				++j;
			}
			else {
				j = next[j];
			}
		}
		delete[] next;
		return j == p.size() ? i - p.size() : -1;
	}
public:
    int strStr(string haystack, string needle) {
		return find(haystack, needle);
    }
};